function fromString(e, n) {
    var r;
    if (16 == n)
        r = 4;
    else if (8 == n)
        r = 3;
    else if (256 == n)
        r = 8;
    else if (2 == n)
        r = 1;
    else if (32 == n)
        r = 5;
    else {
        if (4 != n)
            return void this.fromRadix(e, n);
        r = 2
    }
    this.t = 0,
        this.s = 0;
    for (var i = e.length, o = !1, a = 0; --i >= 0;) {
        var s = 8 == r ? 255 & +e[i] : U(e, i);
        s < 0 ? "-" == e.charAt(i) && (o = !0) : (o = !1,
            0 == a ? this[this.t++] = s : a + r > this.DB ? (this[this.t - 1] |= (s & (1 << this.DB - a) - 1) << a,
                this[this.t++] = s >> this.DB - a) : this[this.t - 1] |= s << a,
        (a += r) >= this.DB && (a -= this.DB))
    }
    8 == r && 0 != (128 & +e[0]) && (this.s = -1,
    a > 0 && (this[this.t - 1] |= (1 << this.DB - a) - 1 << a)),
        this.clamp(),
    o && t.ZERO.subTo(this, this)
}

var B = []
for (P = "0".charCodeAt(0),
         R = 0; R <= 9; ++R)
    B[P++] = R;
for (P = "a".charCodeAt(0),
         R = 10; R < 36; ++R)
    B[P++] = R;
for (P = "A".charCodeAt(0),
         R = 10; R < 36; ++R)
    B[P++] = R;

function log() {
    return B;
}

function U(t, e) {
    var n = B[t.charCodeAt(e)];
    return null == n ? -1 : n
}


function t(t, e, n) {
    null != t && ("number" == typeof t ? this.fromNumber(t, e, n) : null == e && "string" != typeof t ? this.fromString(t, 256) : this.fromString(t, e))
}

t.prototype.toString = function (t) {
    if (this.s < 0)
        return "-" + this.negate().toString(t);
    var e;
    if (16 == t)
        e = 4;
    else if (8 == t)
        e = 3;
    else if (2 == t)
        e = 1;
    else if (32 == t)
        e = 5;
    else {
        if (4 != t)
            return this.toRadix(t);
        e = 2
    }
    var n, i = (1 << e) - 1, o = !1, a = "", s = this.t, c = this.DB - s * this.DB % e;
    if (s-- > 0)
        for (c < this.DB && (n = this[s] >> c) > 0 && (o = !0,
            a = r(n)); s >= 0;)
            c < e ? (n = (this[s] & (1 << c) - 1) << e - c,
                n |= this[--s] >> (c += this.DB - e)) : (n = this[s] >> (c -= e) & i,
            c <= 0 && (c += this.DB,
                --s)),
            n > 0 && (o = !0),
            o && (a += r(n));
    return o ? a : "0"
}
    ,
    t.prototype.negate = function () {
        var e = z();
        return t.ZERO.subTo(this, e),
            e
    }
    ,
    t.prototype.abs = function () {
        return this.s < 0 ? this.negate() : this
    }
    ,
    t.prototype.compareTo = function (t) {
        var e = this.s - t.s;
        if (0 != e)
            return e;
        var n = this.t;
        if (0 != (e = n - t.t))
            return this.s < 0 ? -e : e;
        for (; --n >= 0;)
            if (0 != (e = this[n] - t[n]))
                return e;
        return 0
    }
    ,
    t.prototype.bitLength = function () {
        return this.t <= 0 ? 0 : this.DB * (this.t - 1) + Q(this[this.t - 1] ^ this.s & this.DM)
    }
    ,
    t.prototype.mod = function (e) {
        var n = z();
        return this.abs().divRemTo(e, null, n),
        this.s < 0 && n.compareTo(t.ZERO) > 0 && e.subTo(n, n),
            n
    }
    ,
    t.prototype.modPowInt = function (t, e) {
        var n;
        return n = t < 256 || e.isEven() ? new S(e) : new E(e),
            this.exp(t, n)
    }
    ,
    t.prototype.clone = function () {
        var t = z();
        return this.copyTo(t),
            t
    }
    ,
    t.prototype.intValue = function () {
        if (this.s < 0) {
            if (1 == this.t)
                return this[0] - this.DV;
            if (0 == this.t)
                return -1
        } else {
            if (1 == this.t)
                return this[0];
            if (0 == this.t)
                return 0
        }
        return (this[1] & (1 << 32 - this.DB) - 1) << this.DB | this[0]
    }
    ,
    t.prototype.byteValue = function () {
        return 0 == this.t ? this.s : this[0] << 24 >> 24
    }
    ,
    t.prototype.shortValue = function () {
        return 0 == this.t ? this.s : this[0] << 16 >> 16
    }
    ,
    t.prototype.signum = function () {
        return this.s < 0 ? -1 : this.t <= 0 || 1 == this.t && this[0] <= 0 ? 0 : 1
    }
    ,
    t.prototype.toByteArray = function () {
        var t = this.t
            , e = [];
        e[0] = this.s;
        var n, r = this.DB - t * this.DB % 8, i = 0;
        if (t-- > 0)
            for (r < this.DB && (n = this[t] >> r) != (this.s & this.DM) >> r && (e[i++] = n | this.s << this.DB - r); t >= 0;)
                r < 8 ? (n = (this[t] & (1 << r) - 1) << 8 - r,
                    n |= this[--t] >> (r += this.DB - 8)) : (n = this[t] >> (r -= 8) & 255,
                r <= 0 && (r += this.DB,
                    --t)),
                0 != (128 & n) && (n |= -256),
                0 == i && (128 & this.s) != (128 & n) && ++i,
                (i > 0 || n != this.s) && (e[i++] = n);
        return e
    }
    ,
    t.prototype.equals = function (t) {
        return 0 == this.compareTo(t)
    }
    ,
    t.prototype.min = function (t) {
        return this.compareTo(t) < 0 ? this : t
    }
    ,
    t.prototype.max = function (t) {
        return this.compareTo(t) > 0 ? this : t
    }
    ,
    t.prototype.and = function (t) {
        var e = z();
        return this.bitwiseTo(t, i, e),
            e
    }
    ,
    t.prototype.or = function (t) {
        var e = z();
        return this.bitwiseTo(t, o, e),
            e
    }
    ,
    t.prototype.xor = function (t) {
        var e = z();
        return this.bitwiseTo(t, a, e),
            e
    }
    ,
    t.prototype.andNot = function (t) {
        var e = z();
        return this.bitwiseTo(t, s, e),
            e
    }
    ,
    t.prototype.not = function () {
        for (var t = z(), e = 0; e < this.t; ++e)
            t[e] = this.DM & ~this[e];
        return t.t = this.t,
            t.s = ~this.s,
            t
    }
    ,
    t.prototype.shiftLeft = function (t) {
        var e = z();
        return t < 0 ? this.rShiftTo(-t, e) : this.lShiftTo(t, e),
            e
    }
    ,
    t.prototype.shiftRight = function (t) {
        var e = z();
        return t < 0 ? this.lShiftTo(-t, e) : this.rShiftTo(t, e),
            e
    }
    ,
    t.prototype.getLowestSetBit = function () {
        for (var t = 0; t < this.t; ++t)
            if (0 != this[t])
                return t * this.DB + c(this[t]);
        return this.s < 0 ? this.t * this.DB : -1
    }
    ,
    t.prototype.bitCount = function () {
        for (var t = 0, e = this.s & this.DM, n = 0; n < this.t; ++n)
            t += u(this[n] ^ e);
        return t
    }
    ,
    t.prototype.testBit = function (t) {
        var e = Math.floor(t / this.DB);
        return e >= this.t ? 0 != this.s : 0 != (this[e] & 1 << t % this.DB)
    }
    ,
    t.prototype.setBit = function (t) {
        return this.changeBit(t, o)
    }
    ,
    t.prototype.clearBit = function (t) {
        return this.changeBit(t, s)
    }
    ,
    t.prototype.flipBit = function (t) {
        return this.changeBit(t, a)
    }
    ,
    t.prototype.add = function (t) {
        var e = z();
        return this.addTo(t, e),
            e
    }
    ,
    t.prototype.subtract = function (t) {
        var e = z();
        return this.subTo(t, e),
            e
    }
    ,
    t.prototype.multiply = function (t) {
        var e = z();
        return this.multiplyTo(t, e),
            e
    }
    ,
    t.prototype.divide = function (t) {
        var e = z();
        return this.divRemTo(t, e, null),
            e
    }
    ,
    t.prototype.remainder = function (t) {
        var e = z();
        return this.divRemTo(t, null, e),
            e
    }
    ,
    t.prototype.divideAndRemainder = function (t) {
        var e = z()
            , n = z();
        return this.divRemTo(t, e, n),
            [e, n]
    }
    ,
    t.prototype.modPow = function (t, e) {
        var n, r, i = t.bitLength(), o = Z(1);
        if (i <= 0)
            return o;
        n = i < 18 ? 1 : i < 48 ? 3 : i < 144 ? 4 : i < 768 ? 5 : 6,
            r = i < 8 ? new S(e) : e.isEven() ? new O(e) : new E(e);
        var a = []
            , s = 3
            , c = n - 1
            , u = (1 << n) - 1;
        if (a[1] = r.convert(this),
        n > 1) {
            var l = z();
            for (r.sqrTo(a[1], l); s <= u;)
                a[s] = z(),
                    r.mulTo(l, a[s - 2], a[s]),
                    s += 2
        }
        var f, g, p = t.t - 1, h = !0, d = z();
        for (i = Q(t[p]) - 1; p >= 0;) {
            for (i >= c ? f = t[p] >> i - c & u : (f = (t[p] & (1 << i + 1) - 1) << c - i,
            p > 0 && (f |= t[p - 1] >> this.DB + i - c)),
                     s = n; 0 == (1 & f);)
                f >>= 1,
                    --s;
            if ((i -= s) < 0 && (i += this.DB,
                --p),
                h)
                a[f].copyTo(o),
                    h = !1;
            else {
                for (; s > 1;)
                    r.sqrTo(o, d),
                        r.sqrTo(d, o),
                        s -= 2;
                s > 0 ? r.sqrTo(o, d) : (g = o,
                    o = d,
                    d = g),
                    r.mulTo(d, a[f], o)
            }
            for (; p >= 0 && 0 == (t[p] & 1 << i);)
                r.sqrTo(o, d),
                    g = o,
                    o = d,
                    d = g,
                --i < 0 && (i = this.DB - 1,
                    --p)
        }
        return r.revert(o)
    }
    ,
    t.prototype.modInverse = function (e) {
        var n = e.isEven();
        if (this.isEven() && n || 0 == e.signum())
            return t.ZERO;
        for (var r = e.clone(), i = this.clone(), o = Z(1), a = Z(0), s = Z(0), c = Z(1); 0 != r.signum();) {
            for (; r.isEven();)
                r.rShiftTo(1, r),
                    n ? (o.isEven() && a.isEven() || (o.addTo(this, o),
                        a.subTo(e, a)),
                        o.rShiftTo(1, o)) : a.isEven() || a.subTo(e, a),
                    a.rShiftTo(1, a);
            for (; i.isEven();)
                i.rShiftTo(1, i),
                    n ? (s.isEven() && c.isEven() || (s.addTo(this, s),
                        c.subTo(e, c)),
                        s.rShiftTo(1, s)) : c.isEven() || c.subTo(e, c),
                    c.rShiftTo(1, c);
            r.compareTo(i) >= 0 ? (r.subTo(i, r),
            n && o.subTo(s, o),
                a.subTo(c, a)) : (i.subTo(r, i),
            n && s.subTo(o, s),
                c.subTo(a, c))
        }
        return 0 != i.compareTo(t.ONE) ? t.ZERO : c.compareTo(e) >= 0 ? c.subtract(e) : c.signum() < 0 ? (c.addTo(e, c),
            c.signum() < 0 ? c.add(e) : c) : c
    }
    ,
    t.prototype.pow = function (t) {
        return this.exp(t, new j)
    }
    ,
    t.prototype.gcd = function (t) {
        var e = this.s < 0 ? this.negate() : this.clone()
            , n = t.s < 0 ? t.negate() : t.clone();
        if (e.compareTo(n) < 0) {
            var r = e;
            e = n,
                n = r
        }
        var i = e.getLowestSetBit()
            , o = n.getLowestSetBit();
        if (o < 0)
            return e;
        for (i < o && (o = i),
             o > 0 && (e.rShiftTo(o, e),
                 n.rShiftTo(o, n)); e.signum() > 0;)
            (i = e.getLowestSetBit()) > 0 && e.rShiftTo(i, e),
            (i = n.getLowestSetBit()) > 0 && n.rShiftTo(i, n),
                e.compareTo(n) >= 0 ? (e.subTo(n, e),
                    e.rShiftTo(1, e)) : (n.subTo(e, n),
                    n.rShiftTo(1, n));
        return o > 0 && n.lShiftTo(o, n),
            n
    }
    ,
    t.prototype.isProbablePrime = function (t) {
        var e, n = this.abs();
        if (1 == n.t && n[0] <= x[x.length - 1]) {
            for (e = 0; e < x.length; ++e)
                if (n[0] == x[e])
                    return !0;
            return !1
        }
        if (n.isEven())
            return !1;
        for (e = 1; e < x.length;) {
            for (var r = x[e], i = e + 1; i < x.length && r < C;)
                r *= x[i++];
            for (r = n.modInt(r); e < i;)
                if (r % x[e++] == 0)
                    return !1
        }
        return n.millerRabin(t)
    }
    ,
    t.prototype.copyTo = function (t) {
        for (var e = this.t - 1; e >= 0; --e)
            t[e] = this[e];
        t.t = this.t,
            t.s = this.s
    }
    ,
    t.prototype.fromInt = function (t) {
        this.t = 1,
            this.s = t < 0 ? -1 : 0,
            t > 0 ? this[0] = t : t < -1 ? this[0] = t + this.DV : this.t = 0
    }
    ,
    t.prototype.fromString = function (e, n) {
        var r;
        if (16 == n)
            r = 4;
        else if (8 == n)
            r = 3;
        else if (256 == n)
            r = 8;
        else if (2 == n)
            r = 1;
        else if (32 == n)
            r = 5;
        else {
            if (4 != n)
                return void this.fromRadix(e, n);
            r = 2
        }
        this.t = 0,
            this.s = 0;
        for (var i = e.length, o = !1, a = 0; --i >= 0;) {
            var s = 8 == r ? 255 & +e[i] : U(e, i);
            s < 0 ? "-" == e.charAt(i) && (o = !0) : (o = !1,
                0 == a ? this[this.t++] = s : a + r > this.DB ? (this[this.t - 1] |= (s & (1 << this.DB - a) - 1) << a,
                    this[this.t++] = s >> this.DB - a) : this[this.t - 1] |= s << a,
            (a += r) >= this.DB && (a -= this.DB))
        }
        8 == r && 0 != (128 & +e[0]) && (this.s = -1,
        a > 0 && (this[this.t - 1] |= (1 << this.DB - a) - 1 << a)),
            this.clamp(),
        o && t.ZERO.subTo(this, this)
    }
    ,
    t.prototype.clamp = function () {
        for (var t = this.s & this.DM; this.t > 0 && this[this.t - 1] == t;)
            --this.t
    }
    ,
    t.prototype.dlShiftTo = function (t, e) {
        var n;
        for (n = this.t - 1; n >= 0; --n)
            e[n + t] = this[n];
        for (n = t - 1; n >= 0; --n)
            e[n] = 0;
        e.t = this.t + t,
            e.s = this.s
    }
    ,
    t.prototype.drShiftTo = function (t, e) {
        for (var n = t; n < this.t; ++n)
            e[n - t] = this[n];
        e.t = Math.max(this.t - t, 0),
            e.s = this.s
    }
    ,
    t.prototype.lShiftTo = function (t, e) {
        for (var n = t % this.DB, r = this.DB - n, i = (1 << r) - 1, o = Math.floor(t / this.DB), a = this.s << n & this.DM, s = this.t - 1; s >= 0; --s)
            e[s + o + 1] = this[s] >> r | a,
                a = (this[s] & i) << n;
        for (s = o - 1; s >= 0; --s)
            e[s] = 0;
        e[o] = a,
            e.t = this.t + o + 1,
            e.s = this.s,
            e.clamp()
    }
    ,
    t.prototype.rShiftTo = function (t, e) {
        e.s = this.s;
        var n = Math.floor(t / this.DB);
        if (n >= this.t)
            e.t = 0;
        else {
            var r = t % this.DB
                , i = this.DB - r
                , o = (1 << r) - 1;
            e[0] = this[n] >> r;
            for (var a = n + 1; a < this.t; ++a)
                e[a - n - 1] |= (this[a] & o) << i,
                    e[a - n] = this[a] >> r;
            r > 0 && (e[this.t - n - 1] |= (this.s & o) << i),
                e.t = this.t - n,
                e.clamp()
        }
    }
    ,
    t.prototype.subTo = function (t, e) {
        for (var n = 0, r = 0, i = Math.min(t.t, this.t); n < i;)
            r += this[n] - t[n],
                e[n++] = r & this.DM,
                r >>= this.DB;
        if (t.t < this.t) {
            for (r -= t.s; n < this.t;)
                r += this[n],
                    e[n++] = r & this.DM,
                    r >>= this.DB;
            r += this.s
        } else {
            for (r += this.s; n < t.t;)
                r -= t[n],
                    e[n++] = r & this.DM,
                    r >>= this.DB;
            r -= t.s
        }
        e.s = r < 0 ? -1 : 0,
            r < -1 ? e[n++] = this.DV + r : r > 0 && (e[n++] = r),
            e.t = n,
            e.clamp()
    }
    ,
    t.prototype.multiplyTo = function (e, n) {
        var r = this.abs()
            , i = e.abs()
            , o = r.t;
        for (n.t = o + i.t; --o >= 0;)
            n[o] = 0;
        for (o = 0; o < i.t; ++o)
            n[o + r.t] = r.am(0, i[o], n, o, 0, r.t);
        n.s = 0,
            n.clamp(),
        this.s != e.s && t.ZERO.subTo(n, n)
    }
    ,
    t.prototype.squareTo = function (t) {
        for (var e = this.abs(), n = t.t = 2 * e.t; --n >= 0;)
            t[n] = 0;
        for (n = 0; n < e.t - 1; ++n) {
            var r = e.am(n, e[n], t, 2 * n, 0, 1);
            (t[n + e.t] += e.am(n + 1, 2 * e[n], t, 2 * n + 1, r, e.t - n - 1)) >= e.DV && (t[n + e.t] -= e.DV,
                t[n + e.t + 1] = 1)
        }
        t.t > 0 && (t[t.t - 1] += e.am(n, e[n], t, 2 * n, 0, 1)),
            t.s = 0,
            t.clamp()
    }
    ,
    t.prototype.divRemTo = function (e, n, r) {
        var i = e.abs();
        if (!(i.t <= 0)) {
            var o = this.abs();
            if (o.t < i.t)
                return null != n && n.fromInt(0),
                    void (null != r && this.copyTo(r));
            null == r && (r = z());
            var a = z()
                , s = this.s
                , c = e.s
                , u = this.DB - Q(i[i.t - 1]);
            u > 0 ? (i.lShiftTo(u, a),
                o.lShiftTo(u, r)) : (i.copyTo(a),
                o.copyTo(r));
            var l = a.t
                , f = a[l - 1];
            if (0 != f) {
                var g = f * (1 << this.F1) + (l > 1 ? a[l - 2] >> this.F2 : 0)
                    , p = this.FV / g
                    , h = (1 << this.F1) / g
                    , d = 1 << this.F2
                    , y = r.t
                    , v = y - l
                    , I = null == n ? z() : n;
                for (a.dlShiftTo(v, I),
                     r.compareTo(I) >= 0 && (r[r.t++] = 1,
                         r.subTo(I, r)),
                         t.ONE.dlShiftTo(l, I),
                         I.subTo(a, a); a.t < l;)
                    a[a.t++] = 0;
                for (; --v >= 0;) {
                    var m = r[--y] == f ? this.DM : Math.floor(r[y] * p + (r[y - 1] + d) * h);
                    if ((r[y] += a.am(0, m, r, v, 0, l)) < m)
                        for (a.dlShiftTo(v, I),
                                 r.subTo(I, r); r[y] < --m;)
                            r.subTo(I, r)
                }
                null != n && (r.drShiftTo(l, n),
                s != c && t.ZERO.subTo(n, n)),
                    r.t = l,
                    r.clamp(),
                u > 0 && r.rShiftTo(u, r),
                s < 0 && t.ZERO.subTo(r, r)
            }
        }
    }
    ,
    t.prototype.invDigit = function () {
        if (this.t < 1)
            return 0;
        var t = this[0];
        if (0 == (1 & t))
            return 0;
        var e = 3 & t;
        return (e = (e = (e = (e = e * (2 - (15 & t) * e) & 15) * (2 - (255 & t) * e) & 255) * (2 - ((65535 & t) * e & 65535)) & 65535) * (2 - t * e % this.DV) % this.DV) > 0 ? this.DV - e : -e
    }
    ,
    t.prototype.isEven = function () {
        return 0 == (this.t > 0 ? 1 & this[0] : this.s)
    }
    ,
    t.prototype.exp = function (e, n) {
        if (e > 4294967295 || e < 1)
            return t.ONE;
        var r = z()
            , i = z()
            , o = n.convert(this)
            , a = Q(e) - 1;
        for (o.copyTo(r); --a >= 0;)
            if (n.sqrTo(r, i),
            (e & 1 << a) > 0)
                n.mulTo(i, o, r);
            else {
                var s = r;
                r = i,
                    i = s
            }
        return n.revert(r)
    }
    ,
    t.prototype.chunkSize = function (t) {
        return Math.floor(Math.LN2 * this.DB / Math.log(t))
    }
    ,
    t.prototype.toRadix = function (t) {
        if (null == t && (t = 10),
        0 == this.signum() || t < 2 || t > 36)
            return "0";
        var e = this.chunkSize(t)
            , n = Math.pow(t, e)
            , r = Z(n)
            , i = z()
            , o = z()
            , a = "";
        for (this.divRemTo(r, i, o); i.signum() > 0;)
            a = (n + o.intValue()).toString(t).substr(1) + a,
                i.divRemTo(r, i, o);
        return o.intValue().toString(t) + a
    }
    ,
    t.prototype.fromRadix = function (e, n) {
        this.fromInt(0),
        null == n && (n = 10);
        for (var r = this.chunkSize(n), i = Math.pow(n, r), o = !1, a = 0, s = 0, c = 0; c < e.length; ++c) {
            var u = U(e, c);
            u < 0 ? "-" == e.charAt(c) && 0 == this.signum() && (o = !0) : (s = n * s + u,
            ++a >= r && (this.dMultiply(i),
                this.dAddOffset(s, 0),
                a = 0,
                s = 0))
        }
        a > 0 && (this.dMultiply(Math.pow(n, a)),
            this.dAddOffset(s, 0)),
        o && t.ZERO.subTo(this, this)
    }
    ,
    t.prototype.fromNumber = function (e, n, r) {
        if ("number" == typeof n)
            if (e < 2)
                this.fromInt(1);
            else
                for (this.fromNumber(e, r),
                     this.testBit(e - 1) || this.bitwiseTo(t.ONE.shiftLeft(e - 1), o, this),
                     this.isEven() && this.dAddOffset(1, 0); !this.isProbablePrime(n);)
                    this.dAddOffset(2, 0),
                    this.bitLength() > e && this.subTo(t.ONE.shiftLeft(e - 1), this);
        else {
            var i = []
                , a = 7 & e;
            i.length = 1 + (e >> 3),
                n.nextBytes(i),
                a > 0 ? i[0] &= (1 << a) - 1 : i[0] = 0,
                this.fromString(i, 256)
        }
    }
    ,
    t.prototype.bitwiseTo = function (t, e, n) {
        var r, i, o = Math.min(t.t, this.t);
        for (r = 0; r < o; ++r)
            n[r] = e(this[r], t[r]);
        if (t.t < this.t) {
            for (i = t.s & this.DM,
                     r = o; r < this.t; ++r)
                n[r] = e(this[r], i);
            n.t = this.t
        } else {
            for (i = this.s & this.DM,
                     r = o; r < t.t; ++r)
                n[r] = e(i, t[r]);
            n.t = t.t
        }
        n.s = e(this.s, t.s),
            n.clamp()
    }
    ,
    t.prototype.changeBit = function (e, n) {
        var r = t.ONE.shiftLeft(e);
        return this.bitwiseTo(r, n, r),
            r
    }
    ,
    t.prototype.addTo = function (t, e) {
        for (var n = 0, r = 0, i = Math.min(t.t, this.t); n < i;)
            r += this[n] + t[n],
                e[n++] = r & this.DM,
                r >>= this.DB;
        if (t.t < this.t) {
            for (r += t.s; n < this.t;)
                r += this[n],
                    e[n++] = r & this.DM,
                    r >>= this.DB;
            r += this.s
        } else {
            for (r += this.s; n < t.t;)
                r += t[n],
                    e[n++] = r & this.DM,
                    r >>= this.DB;
            r += t.s
        }
        e.s = r < 0 ? -1 : 0,
            r > 0 ? e[n++] = r : r < -1 && (e[n++] = this.DV + r),
            e.t = n,
            e.clamp()
    }
    ,
    t.prototype.dMultiply = function (t) {
        this[this.t] = this.am(0, t - 1, this, 0, 0, this.t),
            ++this.t,
            this.clamp()
    }
    ,
    t.prototype.dAddOffset = function (t, e) {
        if (0 != t) {
            for (; this.t <= e;)
                this[this.t++] = 0;
            for (this[e] += t; this[e] >= this.DV;)
                this[e] -= this.DV,
                ++e >= this.t && (this[this.t++] = 0),
                    ++this[e]
        }
    }
    ,
    t.prototype.multiplyLowerTo = function (t, e, n) {
        var r = Math.min(this.t + t.t, e);
        for (n.s = 0,
                 n.t = r; r > 0;)
            n[--r] = 0;
        for (var i = n.t - this.t; r < i; ++r)
            n[r + this.t] = this.am(0, t[r], n, r, 0, this.t);
        for (i = Math.min(t.t, e); r < i; ++r)
            this.am(0, t[r], n, r, 0, e - r);
        n.clamp()
    }
    ,
    t.prototype.multiplyUpperTo = function (t, e, n) {
        --e;
        var r = n.t = this.t + t.t - e;
        for (n.s = 0; --r >= 0;)
            n[r] = 0;
        for (r = Math.max(e - this.t, 0); r < t.t; ++r)
            n[this.t + r - e] = this.am(e - r, t[r], n, 0, 0, this.t + r - e);
        n.clamp(),
            n.drShiftTo(1, n)
    }
    ,
    t.prototype.modInt = function (t) {
        if (t <= 0)
            return 0;
        var e = this.DV % t
            , n = this.s < 0 ? t - 1 : 0;
        if (this.t > 0)
            if (0 == e)
                n = this[0] % t;
            else
                for (var r = this.t - 1; r >= 0; --r)
                    n = (e * n + this[r]) % t;
        return n
    }
    ,
    t.prototype.millerRabin = function (e) {
        var n = this.subtract(t.ONE)
            , r = n.getLowestSetBit();
        if (r <= 0)
            return !1;
        var i = n.shiftRight(r);
        (e = e + 1 >> 1) > x.length && (e = x.length);
        for (var o = z(), a = 0; a < e; ++a) {
            o.fromInt(x[Math.floor(Math.random() * x.length)]);
            var s = o.modPow(i, this);
            if (0 != s.compareTo(t.ONE) && 0 != s.compareTo(n)) {
                for (var c = 1; c++ < r && 0 != s.compareTo(n);)
                    if (0 == (s = s.modPowInt(2, this)).compareTo(t.ONE))
                        return !1;
                if (0 != s.compareTo(n))
                    return !1
            }
        }
        return !0
    }
    ,
    t.prototype.square = function () {
        var t = z();
        return this.squareTo(t),
            t
    }
    ,
    t.prototype.gcda = function (t, e) {
        var n = this.s < 0 ? this.negate() : this.clone()
            , r = t.s < 0 ? t.negate() : t.clone();
        if (n.compareTo(r) < 0) {
            var i = n;
            n = r,
                r = i
        }
        var o = n.getLowestSetBit()
            , a = r.getLowestSetBit();
        if (a < 0)
            e(n);
        else {
            o < a && (a = o),
            a > 0 && (n.rShiftTo(a, n),
                r.rShiftTo(a, r));
            var s = function () {
                (o = n.getLowestSetBit()) > 0 && n.rShiftTo(o, n),
                (o = r.getLowestSetBit()) > 0 && r.rShiftTo(o, r),
                    n.compareTo(r) >= 0 ? (n.subTo(r, n),
                        n.rShiftTo(1, n)) : (r.subTo(n, r),
                        r.rShiftTo(1, r)),
                    n.signum() > 0 ? setTimeout(s, 0) : (a > 0 && r.lShiftTo(a, r),
                        setTimeout((function () {
                                e(r)
                            }
                        ), 0))
            };
            setTimeout(s, 10)
        }
    }
    ,
    t.prototype.fromNumberAsync = function (e, n, r, i) {
        if ("number" == typeof n)
            if (e < 2)
                this.fromInt(1);
            else {
                this.fromNumber(e, r),
                this.testBit(e - 1) || this.bitwiseTo(t.ONE.shiftLeft(e - 1), o, this),
                this.isEven() && this.dAddOffset(1, 0);
                var a = this
                    , s = function () {
                    a.dAddOffset(2, 0),
                    a.bitLength() > e && a.subTo(t.ONE.shiftLeft(e - 1), a),
                        a.isProbablePrime(n) ? setTimeout((function () {
                                i()
                            }
                        ), 0) : setTimeout(s, 0)
                };
                setTimeout(s, 0)
            }
        else {
            var c = []
                , u = 7 & e;
            c.length = 1 + (e >> 3),
                n.nextBytes(c),
                u > 0 ? c[0] &= (1 << u) - 1 : c[0] = 0,
                this.fromString(c, 256)
        }
    }


function e(n) {
    var r = t.call(this) || this;
    return n && ("string" == typeof n ? r.parseKey(n) : (e.hasPrivateKeyProperty(n) || e.hasPublicKeyProperty(n)) && r.parsePropertiesFrom(n)),
        r
}

e.prototype.parseKey = function (t) {
    try {
        var e = 0
            , n = 0
            , r = /^\s*(?:[0-9A-Fa-f][0-9A-Fa-f]\s*)+$/.test(t) ? d(t) : y.unarmor(t)
            , i = N.decode(r);
        if (3 === i.sub.length && (i = i.sub[2].sub[0]),
        9 === i.sub.length) {
            e = i.sub[1].getHexStringValue(),
                this.n = L(e, 16),
                n = i.sub[2].getHexStringValue(),
                this.e = parseInt(n, 16);
            var o = i.sub[3].getHexStringValue();
            this.d = L(o, 16);
            var a = i.sub[4].getHexStringValue();
            this.p = L(a, 16);
            var s = i.sub[5].getHexStringValue();
            this.q = L(s, 16);
            var c = i.sub[6].getHexStringValue();
            this.dmp1 = L(c, 16);
            var u = i.sub[7].getHexStringValue();
            this.dmq1 = L(u, 16);
            var l = i.sub[8].getHexStringValue();
            this.coeff = L(l, 16)
        } else {
            if (2 !== i.sub.length)
                return !1;
            var f = i.sub[1].sub[0];
            e = f.sub[0].getHexStringValue(),
                this.n = L(e, 16),
                n = f.sub[1].getHexStringValue(),
                this.e = parseInt(n, 16)
        }
        return !0
    } catch (t) {
        return !1
    }
}
    ,
    e.prototype.getPrivateBaseKey = function () {
        var t = {
            array: [new et.asn1.DERInteger({
                int: 0
            }), new et.asn1.DERInteger({
                bigint: this.n
            }), new et.asn1.DERInteger({
                int: this.e
            }), new et.asn1.DERInteger({
                bigint: this.d
            }), new et.asn1.DERInteger({
                bigint: this.p
            }), new et.asn1.DERInteger({
                bigint: this.q
            }), new et.asn1.DERInteger({
                bigint: this.dmp1
            }), new et.asn1.DERInteger({
                bigint: this.dmq1
            }), new et.asn1.DERInteger({
                bigint: this.coeff
            })]
        };
        return new et.asn1.DERSequence(t).getEncodedHex()
    }
    ,
    e.prototype.getPrivateBaseKeyB64 = function () {
        return g(this.getPrivateBaseKey())
    }
    ,
    e.prototype.getPublicBaseKey = function () {
        var t = new et.asn1.DERSequence({
            array: [new et.asn1.DERObjectIdentifier({
                oid: "1.2.840.113549.1.1.1"
            }), new et.asn1.DERNull]
        })
            , e = new et.asn1.DERSequence({
            array: [new et.asn1.DERInteger({
                bigint: this.n
            }), new et.asn1.DERInteger({
                int: this.e
            })]
        })
            , n = new et.asn1.DERBitString({
            hex: "00" + e.getEncodedHex()
        });
        return new et.asn1.DERSequence({
            array: [t, n]
        }).getEncodedHex()
    }
    ,
    e.prototype.getPublicBaseKeyB64 = function () {
        return g(this.getPublicBaseKey())
    }
    ,
    e.wordwrap = function (t, e) {
        if (!t)
            return t;
        var n = "(.{1," + (e = e || 64) + "})( +|$\n?)|(.{1," + e + "})";
        return t.match(RegExp(n, "g")).join("\n")
    }
    ,
    e.prototype.getPrivateKey = function () {
        var t = "-----BEGIN RSA PRIVATE KEY-----\n";
        return t += e.wordwrap(this.getPrivateBaseKeyB64()) + "\n",
            t += "-----END RSA PRIVATE KEY-----"
    }
    ,
    e.prototype.getPublicKey = function () {
        var t = "-----BEGIN PUBLIC KEY-----\n";
        return t += e.wordwrap(this.getPublicBaseKeyB64()) + "\n",
            t += "-----END PUBLIC KEY-----"
    }
    ,
    e.hasPublicKeyProperty = function (t) {
        return (t = t || {}).hasOwnProperty("n") && t.hasOwnProperty("e")
    }
    ,
    e.hasPrivateKeyProperty = function (t) {
        return (t = t || {}).hasOwnProperty("n") && t.hasOwnProperty("e") && t.hasOwnProperty("d") && t.hasOwnProperty("p") && t.hasOwnProperty("q") && t.hasOwnProperty("dmp1") && t.hasOwnProperty("dmq1") && t.hasOwnProperty("coeff")
    }
    ,
    e.prototype.parsePropertiesFrom = function (t) {
        this.n = t.n,
            this.e = t.e,
        t.hasOwnProperty("d") && (this.d = t.d,
            this.p = t.p,
            this.q = t.q,
            this.dmp1 = t.dmp1,
            this.dmq1 = t.dmq1,
            this.coeff = t.coeff)
    }


var at = function() {
    function t(t) {
        t = t || {},
            this.default_key_size = t.default_key_size ? parseInt(t.default_key_size, 10) : 1024,
            this.default_public_exponent = t.default_public_exponent || "010001",
            this.log = t.log || !1,
            this.key = null
    }
    t.prototype.setKey = function(t) {
        this.log && this.key
            // this.key = new it(t)
    }
        ,
        t.prototype.setPrivateKey = function(t) {
            this.setKey(t)
        }
        ,
        t.prototype.setPublicKey = function(t) {
            this.setKey(t)
        }
        ,
        t.prototype.decrypt = function(t) {
            try {
                return this.getKey().decrypt(p(t))
            } catch (t) {
                return !1
            }
        }

        t.prototype.encrypt = function(t) {
            try {
                return g(this.getKey().encrypt(t))
            } catch (t) {
                return !1
            }
        }

        t.prototype.sign = function(t, e, n) {
            try {
                return g(this.getKey().sign(t, e, n))
            } catch (t) {
                return !1
            }
        }

        t.prototype.verify = function(t, e, n) {
            try {
                return this.getKey().verify(t, p(e), n)
            } catch (t) {
                return !1
            }
        }

        t.prototype.getKey = function(t) {
            if (!this.key) {
                if (this.key = new it,
                t && "[object Function]" === {}.toString.call(t))
                    return void this.key.generateAsync(this.default_key_size, this.default_public_exponent, t);
                this.key.generate(this.default_key_size, this.default_public_exponent)
            }
            return this.key
        }

        t.prototype.getPrivateKey = function() {
            return this.getKey().getPrivateKey()
        }

        t.prototype.getPrivateKeyB64 = function() {
            return this.getKey().getPrivateBaseKeyB64()
        }

        t.prototype.getPublicKey = function() {
            return this.getKey().getPublicKey()
        }

        t.prototype.getPublicKeyB64 = function() {
            return this.getKey().getPublicBaseKeyB64()
        }

        t.version = ot.version;
        return t
}();
